Optimal Bidding Algorithms Against Cheating in Multiple-Object Auctions

摘要

This paper studies some basic problems in a multiple-object auction modelusing methodologies from theoretical computer science. We are especiallyconcerned with situations where an adversary bidder knows the biddingalgorithms of all the other bidders. In the two-bidder case, we derive anoptimal randomized bidding algorithm, by which the disadvantaged bidder canprocure at least half of the auction objects despite the adversary's a prioriknowledge of his algorithm. In the general $k$-bidder case, if the number ofobjects is a multiple of $k$, an optimal randomized bidding algorithm is found.If the $k-1$ disadvantaged bidders employ that same algorithm, each of them canobtain at least $1/k$ of the objects regardless of the bidding algorithm theadversary uses. These two algorithms are based on closed-form solutions tocertain multivariate probability distributions. In situations where aclosed-form solution cannot be obtained, we study a restricted class of biddingalgorithms as an approximation to desired optimal algorithms.